package interview.buildbinarytree;

import interview.common.BinaryTreeNode;

public class BuildBinaryTree {
	public BinaryTreeNode build(int[] inorder, int[] postorder) {
		return buildTreeRecursive(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
	}

	private BinaryTreeNode buildTreeRecursive(int[] inorder, int iStart, int iEnd,
			int[] postorder, int pStart, int pEnd) {
		if(iStart == iEnd) {
			BinaryTreeNode leaf = new BinaryTreeNode();
			leaf.setData(inorder[iStart]);
			leaf.setLeft(null);
			leaf.setRight(null);
			return leaf;
		} else if (iStart > iEnd) {
			return null;
		}
		
		BinaryTreeNode root = new BinaryTreeNode();
		root.setData(postorder[pEnd]);
		int mid = -1;
		for(int i = iStart; i <= iEnd; i++) {
			if(inorder[i] == postorder[pEnd]) {
				mid = i;
				break;
			}
		}
		root.setLeft(buildTreeRecursive(inorder, iStart, mid - 1, postorder, pStart, mid - 1));
		root.setRight(buildTreeRecursive(inorder, mid + 1, iEnd, postorder, mid, pEnd - 1));
		return root;
	}
}
